from heapq import heappush, heappop

class Solution:
    def __init__(self):
        self.heap = []
        self.last = 0
        heappush(self.heap, 1)

    def nthUglyNumber(self, n: int) -> int:
        val = heappop(self.heap)
        while val == self.last:
            val = heappop(self.heap)
        self.last = val
        if n == 1:
            return val
        heappush(self.heap, val * 2)
        heappush(self.heap, val * 3)
        heappush(self.heap, val * 5)
        return self.nthUglyNumber(n-1)

if __name__ == "__main__":
    print(Solution().nthUglyNumber(10))
